package leetcode.jianzhioffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-16 16:57
 **/
public class JianZhiOffer38 {

    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        List<String> list = new ArrayList<>();
        do {
            list.add(new String(chars));
        } while (nextPermutation(chars));

        String[] strs = new String[list.size()];
        int index = 0;
        for (String s1 : list) {
            strs[index++] = s1;
        }
        return strs;
    }

    private boolean nextPermutation(char[] chars) {
        int i = chars.length - 2;
        while (i >= 0 && chars[i] >= chars[i + 1]) {
            i--;
        }
        if (i == -1) {
            return false;
        }
        int j = chars.length - 1;
        while (j >= 0 && chars[j] <= chars[i]) {
            j--;
        }
        swap(chars, i , j);
        reverse(chars, i + 1);
        return true;
    }

    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    private void reverse(char[] chars, int i) {
        int end = chars.length - 1;
        while (i < end) {
            char temp = chars[i];
            chars[i] = chars[end];
            chars[end] = temp;
            i++;
            end--;
        }
    }
}
